package com.techyuan.algorithm.dp;


import javafx.util.Pair;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Administrator on 2017/2/22.
 */
public class OptimalBST {
    public static Pair<int[][], double[][]> optimalBst(double[] p, double[] q, int n) {
        int[][] root = new int[n + 1][n + 1];
        double[][] e = new double[n + 1][n + 1];
        double[][] w = new double[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            e[i][i - 1] = q[i - 1];
            w[i][i - 1] = q[i - 1];
        }

        for (int l = 1; l <= n; l++) {
            for (int i = 1; i < n - l + 1; i++) {
                int j = l + i - 1;
                e[i][j] = Double.MAX_VALUE;
                w[i][j] = w[i][j - 1] + p[j] + q[j];
                for (int r = i; r <= j; r++) {
                    double t = e[i][r - 1] + e[r + 1][j] + w[i][j];
                    if (t < e[i][j]) {
                        e[i][j] = t;
                        root[i][j] = r;
                    }
                }
            }
        }
        return new Pair<int[][], double[][]>(root, e);
    }

    public static void main(String[] args) {
        double[] p = new double[]{0.0, 0.15, 0.10, 0.05, 0.10, 0.20};
        double[] q = new double[]{0.05, 0.10, 0.05, 0.05, 0.05, 0.10};
        int n = 6;
        Pair<int[][], double[][]> ret = optimalBst(p, q, n);
        int[][] R = ret.getKey();
        for(int i = 0;i < R.length;i++)
        {
            for(int j = 0;j < R.length;j++)
                System.out.print(R[i][j] + "　　");
            System.out.println();
        }
    }
}
